\chapter*{Introduction}
\markboth{Introduction}{Introduction}
\addcontentsline{toc}{chapter}{Introduction}

\begin{flushright}
\sl
As many more individuals of each species are born than can possibly survive, and as consequently there is a frequently recurring struggle for existence, it follows that any being, if it vary in any manner profitable to itself, under the complex and sometimes varying conditions of life, will have a better chance of survival and thus be naturally selected. From the strong principle of inheritance, any selected variety will tend to propagate its new and modified form. [Introduction, p. 5]
\end{flushright}

\begin{flushright}
\sl
C. Darwin, \textit{Origin of Species}
\end{flushright}

\par\vfill\par


The \textit{High-Level Synthesis} (HLS) is concerned with the design and 
implementation of digital circuits starting from a behavioral description, 
subject to a set of goals and constraints, and given a library of different 
types of resources.

% The behavioral description specifies behavior in terms of operations, 
% assignment statements and control constructs in a common high-level language 
% (e.g. C language). The resource library provides a choice of components among 
% which the synthesizer may select the one that best matches the design 
% constraints and maximizes the optimization objectives. 
% The overall target architecture of the HLS flow is typically based on the FSMD 
% model \cite{Gajski}: a datapath description controlled by a finite state machine. 
% At the RTL level, a datapath is composed of functional units, storage and 
% interconnection elements. The finite state machine specifies every set of 
% micro-operations for the datapath to be performed during each control step. 

The high-level synthesis involves three main tasks:
\begin{enumerate}
 \item \emph{Operation scheduling}: it provides the cycle steps in which operations start their execution.
\item \emph{Resource allocation}: it is concerned with assigning operations 
and values to hardware components and interconnecting them using connection 
elements. Solving these problems efficiently is a non-trivial matter because of 
their NP-complete nature~\cite{np_complete}. 
\item \emph{Controller synthesis}: it provides the logic to issue datapath operations, 
based on the control flow.
\end{enumerate}

Recent studies \cite{interconnection_cong} have demonstrated that interconnection 
costs have to be taken into account since area of multiplexers and 
interconnection elements has by far outweighed area of functional units and 
registers. %(see Table \ref{tab:interconnect}). 
This is especially true for FPGA designs because a larger amount of transistors have to be provided in the 
wiring channels and logic blocks to provide programmability for signal 
transmission. This strongly motivates the design of highly effective algorithms 
to reduce the amount and size of multiplexers generated during the high-level 
synthesis: a methodology that does not consider them produces an incomplete area 
estimation. This could lead to a wrong final design, where interconnection 
elements could increase area costs also over global constraints.
In fact, sometimes design with more functional units or registers can reduce 
total area, by far reducing interconnection elements. As a result, 
interconnection allocation should be taken into account by each methodology 
that tries to minimize FPGA design.

\ \\
The goal of this thesis is to produce a methodology to approach the high-level synthesis problem that is able to take into account the contribution of area given by interconnection elements. The methodology has to perform design space exploration in order to find solutions that reduce the overall area requested by the final design.

Evolutionary algorithms are good candidates for high-level synthesis and design space exploration
because they iteratively improve a set of solutions (thus improving alternative 
designs), they do not require the quality (cost) function to be linear 
(e.g.: time-area product) and they are known to work well on problems with 
large and non-convex search spaces (constrained or with poor information). 
They can build a model \textit{themselves} to give estimations on the final 
solution.

The high-level synthesis cost function considered is composed by two objectives to be optimized simultaneously: area and performance. A model has been proposed to give estimations of objective values for the solution resulting from the flow. The model is oriented to estimate the values obtained from the synthesis on FPGA devices.

Since the function to be optimized is a multi-objective one, the proposed approach adopts a non-dominated sorting genetic algorithm (NSGA-II \cite{deb00fast}), since it is able to maintain diversity into the population and therefore it allows a better exploration of the design space in multi-objective problems since the different objectives are not weighted to form a single objective function, but they are all considered at the same level of importance.
Besides, there is not a single solution to such problems, no optimum in the sense 
traditionally expected. Instead, there is a large family of alternative solutions, 
different balances of the various objectives. Then, the solution that best fits the area contraints imposed by the target device, can be selected among them.

The main contributions of this work are the following:
\begin{itemize}
 \item the \textbf{high-level synthesis flow} is able to translate the behavioral specification from C language directly to a simulable and synthetisable RTL design, that can be described with different hardware description languages (e.g. SystemC, VHDL or Verilog);
\item the \textbf{model}, that has been used to evaluate the results coming from the high-level synthesis, presents a low error with respect to the real values coming from the synthesis on FPGA devices;
\item the algorithm for \textbf{design space exploration}, based on a genetic algorithm and integrating the features of the NSGA-II algorithm, is able to deal with multi-objective optimizations. Then, since it integrates the high-level synthesis flow proposed as fitness function evaluation, it is able to consider all the components composing the final design. In a such way, the interconnection elements are taken in account and they can be reduced with a proper binding of operations to the functional units.
\end{itemize}

\ \\

This thesis is organized as follows. In Chapter~\ref{preliminaries}, the high-level synthesis problem is formulated and formalized and the main elements composing a genetic algorithm are presented. Chapter~\ref{state_art} provides an overview of the current state of the art of the high-level synthesis techniques and genetic algorithms (e.g. the NSGA-II algorithm). Approaches integrating evolutionary algorithms in a high-level synthesis flow are presented as well. In Chapter~\ref{mixed} the proposed mixed flow for high-level synthesis of a design solution is presented and implementation choises are motivated. Then, in Chapter~\ref{details}, the high-level synthesis flow and the design space exploration are detailed. Each sub-tasks has been analysed and described to understand as it has been implemented. Experimental results are reported in Chapter~\ref{results}. In the end, in Chapter~\ref{conclusions}, the proposed methodolody is commented and possible future works are proposed to extend its capabilities.
